package com.cdream.basic.algorithm.leetcode.sort;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cdream
 * @date 2022/2/19
 */
public class Question969 {
    public static void main(String[] args) {
        new Question969().pancakeSort(new int[]{3,2,4,1});
    }
    public List<Integer> pancakeSort(int[] arr) {
        List<Integer> res = new ArrayList<>();
        int max = arr.length;
        while(max!=1){
            for(int i = 0; i<arr.length;i++){
                // 如果在自己的位置不用动
                if(max==arr[i] && i+1==arr[i]){
                    max--;
                }
                // 不在自己的位置上，如果在第一个，直接反转
                if(max==arr[i] && arr[i]!=i+1){
                    if(i!=0){
                        swap(arr,0,i);
                        res.add(i);
                    }
                    swap(arr,0,max-1);
                    res.add(max-1);
                    max--;
                    break;
                }
            }
        }
        return res;
    }
    public void swap(int[] arr, int start, int end){
        while(start<end){
            int temp = arr[start];
            arr[start++] = arr[end];
            arr[end--] = temp;
        }
    }
}
